In modern system-on-chip design, supply-voltage-noise induced reliability issues are becoming increasingly challenging due to increase in current density (Document 1). Among the various sources of voltage noise. IR drop refers to the resistive voltage drop across metal wires in the power delivery network (PDN). Typical design rules tolerate an IR drop ratio no more than 5% of supply voltage, and violations can lead to timing errors.
In a flip-chip design, because the underlying silicon chip has a non-uniform power dissipation, the number and locations of controlled-collapse-chip-connection (C4) pads connecting to the on-chip PDN have a large impact on the IR drop. Thus, optimizing both the number and locations of power supply C4 pads becomes critical to guarantee the desired IR drop target. Moreover, given the fact that both power supply and signal I/O share the same physical interface—C4 pads—determining the minimum number of power pads required for a given chip design through such optimization can help a designer to determine the available I/O bandwidth, or even perform tradeoffs between I/O bandwidth and the IR drop target.
Previous works have addressed a pad placement optimization for the purpose of minimizing IR drop (Documents 2-4). However, their approaches have scalability limitations, and as a result, they are not suitable for the large pad placement design space of modern systems. Some other works provide analytical methods to estimate the maximum IR drop when pad number and pad locations are given (Documents 5 and 6). It is known that no existing work investigates the minimum number of C4 pads required to satisfy a target IR drop in a 2D PDN grid.
In the present invention, a fast method is proposed to obtain the minimum pad number for a target IR drop and corresponding optimized pad locations.
First, a new method of power pad placement optimization, Walking Pads (WP), is introduced. The key idea behind WP is to convert a global optimization problem (the placement of n pads given m candidate locations) into a local balance problem (the placement of individual pads (current sources) with respect to various nearby current demands). Treating pads as “mobile positive charges” and the on-chip PDN grid as a 2D electrostatic voltage field, WP optimizes pad locations by letting each of the pads “walk” in the direction of the total virtual force exerted upon it to achieve local force balance.
WP achieves significant speedup over existing methods in the literature, because it has two significant advantages:                WP leverages the underlying voltage gradients to quickly identify promising pad locations; and        WP allows all pads to step toward their balanced positions simultaneously, reducing algorithm complexity significantly as a function of target pad count.        
Second, an analytical formula is derived to describe the relationship between IR drop and pad number based on optimized pad locations. While not a closed-form model, the proposed analytical formula only requires that three coefficients to be fitted to a curve, and can predict the optimal pad count to within an error of two pads for systems with 128-1024 pads. When combined with WP, the proposed analytical formula can quickly and accurately predict the minimum required pad count.
The present invention makes two principal contributions:                WP is proposed, and it is demonstrated that it achieves at least 100× speedup with respect to the classical simulated annealing (SA) methods in the literature, while sacrificing no more than 0. 1% VDD in steadystate IR drop; and        An analytical formula, that describes the relationship between the number of pads and the expected maximum IR drop assuming optimized pad locations, is proposed.        
Together, the analytical model and WP algorithm are positioned to significantly accelerate the optimization of power pad count and placement, and therefore, create new opportunities for joint optimizations.